//给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。
//
// 单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
//
// 示例 1：
//
//
//输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f",
//"l","v"]], words = ["oath","pea","eat","rain"]
//输出：["eat","oath"]
//
//
// 示例 2：
//
//
//输入：board = [["a","b"],["c","d"]], words = ["abcb"]
//输出：[]
//
// 提示：
//
// m == board.length
// n == board[i].length
// 1 <= m, n <= 12
// board[i][j] 是一个小写英文字母
// 1 <= words.length <= 3 * 10⁴
// 1 <= words[i].length <= 10
// words[i] 由小写英文字母组成
// words 中的所有字符串互不相同
//
// Related Topics 字典树 数组与矩阵 字符串 回溯与递归 矩阵 👍 761 👎 0


//? 类似于单词搜索I的解法 有问题
function findWords(board: string[][], words: string[]): string[] {

    function backtracking(x,y,word,t) {
        //? 这里如果用数组 则每个符合条件的值会push四次(无论输入是什么都是四次) 显然跟四次并递归有关这是为什么？
        if (t >= word.length) {
            res.push(word)
        }
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] !== word[t] || board[x][y] === "#") return false
        let tmp = board[x][y]
        board[x][y] = '#'
        let result = backtracking(x + 1, y, word, t + 1) || backtracking(x, y + 1, word,t + 1) || backtracking(x- 1, y, word, t + 1) || backtracking(x, y - 1, word, t + 1)
        if (result) return true
        board[x][y] = tmp
        return false
    }

    let res : string[] = []
    for (let k = 0; k < words.length; k++) {
        for (let i = 0; i < board.length; i ++) {
            for (let j = 0; j < board[0].length; j ++) {
                //? 需要找到开头的字符
                if (board[i][j] === words[k][0]) {
                    backtracking(i,j,words[k],0)
                }
            }
        }
    }
    return Array.from(res)
};

//? 前缀树解法
function findWords2(board: string[][], words: string[]): string[] {

    //? 存放最终结果集
    let res = [];
    //? 字典树节点
    class TrieNode {
        end: boolean;
        child: {};
        constructor() {
            this.end = false;
            this.child = {};
        }
    }
    //? 最终形成的字典树根节点
    let root = null;
    let Trie = function () {
        root = new TrieNode();
    };
    //? 建立字典树的函数
    Trie.prototype.insert = (word) => {
        let cur = root;
        for (let i = 0; i < word.length; i++) {
            if (!cur.child[word[i]]) {
                cur.child[word[i]] = new TrieNode();
            }
            cur = cur.child[word[i]];
        }
        cur.end = true;
    };
    //? 创建根节点
    let trie = new Trie();
    //? 进行建树操作
    for (let i = 0; i < words.length; i++) {
        trie.insert(words[i]);
    }
    let dfs = (x, y, t, cur) => {
        if (cur.end) {
            res.push(t);
            cur.end = false; //? 避免重复计算
        }
        //? 剪枝条件：1.边界处理 2.下一步是否可走 3.下一步字典树是否可走
        if (
            x < 0 ||
            x >= board.length ||
            y < 0 ||
            y >= board[0].length ||
            board[x][y] == "#" ||
            !cur.child[board[x][y]]
        )
            return;
        let tmp = board[x][y];
        board[x][y] = "#"; //? 走
        cur = cur.child[tmp];
        dfs(x + 1, y, t + tmp, cur); //? 上下左右四个方向遍历
        dfs(x, y + 1, t + tmp, cur);
        dfs(x - 1, y, t + tmp, cur);
        dfs(x, y - 1, t + tmp, cur);
        board[x][y] = tmp; //? 回溯与递归（还原）
    };
    //? 对单词表进行全局搜索
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            dfs(i, j, "", root);
        }
    }
    return res;
};
